package com.shiguiwu.springmybatis.algorithm.tree;

import lombok.Data;
import lombok.extern.slf4j.Slf4j;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * @description: 赫夫曼树，也叫最优二叉树，也就是wpl即树的带权路径长度规定为所有叶子结点的带权路径长度之和最小
 * 树的带权路径长度： 节点的权与节点路径长度之积
 * @author: stone
 * @date: Created by 2023/1/15 15:16
 * @version: 1.0.0
 * @pakeage: com.shiguiwu.springmybatis.algorithm.tree
 */
@Slf4j
public class HuffmanTree {

    public static void main(String[] args) {

        int arr[] = { 13, 7, 8, 3, 29, 6, 1 };
        Node root = createHuffmanTree(arr);

        System.out.println("---------不美丽的分割线-----------");
        // 测试
        root.preOrder();
    }

    /**
     *  创建赫夫曼树
     * @param arr 数组
     * @return  返回创建赫夫曼树
     */
    private static Node createHuffmanTree(int[] arr) {
        //将数组转成列表
        List<Node> nodes = Arrays.stream(arr).boxed().map(Node::new).collect(Collectors.toList());

        // 【2】循环处理分析得四步骤，故，最终返回的只有一个 root 节点
        while (nodes.size() > 1) {
            // 1、从小到大排序(每次循环都要排序一次)
            Collections.sort(nodes);
            log.info("当前的节点 ===> {}", nodes);

            // 2、取出根节点权值最小的两颗二叉树，然后合并
            Node left = nodes.get(0);
            Node right = nodes.get(1);

            //合并
            Node parent  = new Node(left.val + right.val);
            parent .left = left;
            parent .right = right;

            //合并以后删除
            // 3、从 nodes 集合中删除已经处理过的二叉树
            nodes.remove(left);
            nodes.remove(right);

            // 4、将 合并出来的二叉树 parent 加入到 nodes集合中
            nodes.add(parent);
        }
        return nodes.get(0);
    }



    @Data
    public static class Node implements Comparable<Node> {
        protected Integer val;
        protected Node left;
        protected Node right;

        public Node() {
        }

        public Node(Integer val) {
            this.val = val;
        }

        // 前序遍历
        public void preOrder() {
            System.out.println(this);

            if (this.left != null) {
                this.left.preOrder();
            }

            if (this.right != null) {
                this.right.preOrder();
            }
        }


        @Override
        public String toString() {
            return "Node{" +
                    "val=" + val +
                    '}';
        }

        @Override
        public int compareTo(Node o) {
            return this.val - o.val;
        }
    }
}
